package OfferZ001;

/**
 * 整数除法
 * 给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。
 *
 * @author 23737
 * @time 2021.11.11
 */
public class Test {
    public static void main(String[] args) {
        int a = 8;
        int b = 2;
        System.out.println(a >> b);
        System.out.println(a << b);
    }
}

class Solution {
    public int divide(int a, int b) {
        if (a == -2147483648 && b == -1) {
            return 2147483647;
        } else {
            return a / b;
        }
    }

    // 因为将 -2147483648 转成正数会越界，但是将 2147483647 转成负数，则不会
    // 所以，我们将 a 和 b 都转成负数
    // 时间复杂度：O(n)，n 是最大值 2147483647 --> 10^10 --> 超时
    public int divide2(int a, int b) {
        // 32 位最大值：2^31 - 1 = 2147483647
        // 32 位最小值：-2^31 = -2147483648
        // -2147483648 / (-1) = 2147483648 > 2147483647 越界了

        if (a == Integer.MIN_VALUE && b == -1)
            return Integer.MAX_VALUE;

        // ab若为一正一负则返回-1
        int sign = (a > 0) ^ (b > 0) ? -1 : 1;
        // 环境只支持存储 32 位整数
        if (a > 0) a = -a;
        if (b > 0) b = -b;
        int res = 0;

        // 使用减法代替除法
        while (a <= b) {
            a -= b;
            res++;
        }
        return sign == 1 ? res : -res;
    }

}
